import java.util.LinkedList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=20 lang=java
 *
 * [20] 有效的括号
 *
 * https://leetcode-cn.com/problems/valid-parentheses/description/
 *
 * algorithms
 * Easy (36.22%)
 * Total Accepted:    44.3K
 * Total Submissions: 122.2K
 * Testcase Example:  '"()"'
 *
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * 
 * 有效字符串需满足：
 * 
 * 
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 
 * 
 * 注意空字符串可被认为是有效字符串。
 * 
 * 示例 1:
 * 
 * 输入: "()"
 * 输出: true
 * 
 * 
 * 示例 2:
 * 
 * 输入: "()[]{}"
 * 输出: true
 * 
 * 
 * 示例 3:
 * 
 * 输入: "(]"
 * 输出: false
 * 
 * 
 * 示例 4:
 * 
 * 输入: "([)]"
 * 输出: false
 * 
 * 
 * 示例 5:
 * 
 * 输入: "{[]}"
 * 输出: true
 * 
 */
class Solution {
    private static final Map<Character, Character> VALID_PARENTHESES_MAP = new HashMap<>();
	
	static {
		VALID_PARENTHESES_MAP.put('(', ')');
		VALID_PARENTHESES_MAP.put('[', ']');
		VALID_PARENTHESES_MAP.put('{', '}');
	}
	
    public boolean isValid(String s) {
    	LinkedList<Character> stack = new LinkedList<>();
        for (int i=0; i<s.length(); ++i) {
        	Character cur = s.charAt(i);
            if (stack.isEmpty()) {
                stack.push(cur);
            } else {
            	Character last = stack.getFirst();
            	Character shouldBe = VALID_PARENTHESES_MAP.get(last);
            	if (cur.equals(shouldBe)) {
            		stack.pop();
            	} else {
            		stack.push(cur);
            	}
            }
        }
        return stack.isEmpty();
    }
}
